package linked;

import linked.base.ListNode;

public class Solution_25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode firNode = new ListNode();
        firNode.next = head;
        ListNode curNode = head;
        ListNode nextNode = head;
        ListNode preNode = firNode;
        while (nextNode != null) {
            for (int i = 0; i < k && nextNode != null; i++) {
                nextNode = nextNode.next;
            }
            ListNode tmpNode = curNode;
            while (curNode != null) {
                ListNode tmp = curNode.next;
                curNode.next = preNode;
                preNode = curNode;
                curNode = tmp;
            }
            tmpNode.next = nextNode;
        }
        return firNode.next;
    }


    //TODO
    /**
     *  这段才是正确做法
     */
    public ListNode reverseKGroup1(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;          // 已处理段的尾巴
        while (head != null) {
            ListNode tail = head;      // 待反转段的头部（反转后变成尾部）
            // 1. 走 k-1 步找到第 k 个节点
            for (int i = 0; i < k; i++) {
                if (tail == null) {    // 不足 k 个，直接返回
                    return dummy.next;
                }
                tail = tail.next;
            }
            // 2. 反转 head 到 tail 前驱这一段（共 k 个）
            ListNode prev = null, cur = head, next;
            while (cur != tail) {      // 只反转到 tail 之前
                next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }
            // 3. 把反转后的子段接回去
            pre.next = prev;           // prev 现在是新头
            head.next = tail;          // 反转后的尾巴连到下一段
            // 4. 移动指针到下一轮
            pre = head;                // 新的尾巴是刚才的 head
            head = tail;               // 从 tail 开始下一段
        }
        return dummy.next;
    }


}
